struct Hash {
	static const int mask = 0x7fff;
	int p[32768], q[32768];

	void clear() {
		for (int i = 0; i <= mask; ++i) {
			q[i] = -1;
		}
	}

	int& operator[](int k) {
		int i = k & mask;
		for (int j = 0; q[i] != -1 && p[i] != k; i = (i + 1) & mask) 			{
			continue;
		}
		p[i] = k;
		return q[i];
	}
} hash;
struct shashmap
{
    //Length of the hash table = MASK+1
    static const int MASK = 0x7ffff;
    static const int NIL = 0x7fffffff;
    int key[MASK+1], value[MASK+1];

    void init()
    {for (int i = 0; i <= MASK; ++i) key[i] = value[i] = NIL;}

    shashmap()
    {init();}

    //Hash Function
    inline int hash(int k, int i)
    {return (k+i) & MASK;}

    int insert(int k, int v)
    {
        int h;
        for (int i = 0; i <= MASK; ++i)
        {
            h = hash(k, i);
            if (key[h]==NIL)
            {
                key[h] = k;
                return value[h] = v;
            }
        }
    }

    int find(int k)
    {
        int h;
        for (int i = 0; i <= MASK; ++i)
        {
            h = hash(k, i);
            if (key[h]==k || key[h]==NIL) return value[h];
        }
    }

    int& operator [] (int k)
    {
        int h;
        for (int i = 0; i <= MASK; ++i)
        {
            h = hash(k, i);
            if (key[h]==k || key[h]==NIL) return value[h];
        }
    }
};
